package com.c2b.algorithm.leetcode.lcr;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href='https://leetcode.cn/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/'>将二叉搜索树转化为排序的双向链表(Convert Binary Search Tree to Sorted Doubly-Linked-List)</a>
 * <p>将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。</p>
 * <p>对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。</p>
 * <p>特别地，我们希望可以 就地 完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中最小元素的指针。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * <a href='https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/description/'>查看示例</a>
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>-1000 <= Node.val <= 1000</li>
 *     <li>Node.left.val < Node.val < Node.right.val</li>
 *     <li>Node.val 的所有值都是独一无二的</li>
 *     <li>0 <= Number of Nodes <= 2000</li>
 * </ul>
 *
 * </p>
 *
 * @author c2b
 * @since 2024/3/20 15:01
 */
public class LCR155 {

    static class Solution {
        public Node treeToDoublyList(Node root) {
            if (root == null) {
                return null;
            }
            Deque<Node> stack = new LinkedList<>();
            Node head = null;
            Node prev = null;
            while (root != null || !stack.isEmpty()) {
                while (root != null) {
                    stack.addLast(root);
                    root = root.left;
                }
                root = stack.removeLast();
                if (head == null) {
                    head = root;
                }
                if (prev != null) {
                    root.left = prev;
                    prev.right = root;
                }
                prev = root;
                root = root.right;
            }
            prev.right = head;
            head.left = prev;
            return head;
        }
    }

    static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }
}
